package com.cqs.leetcode.backtrack;

import com.google.common.collect.Lists;

import java.util.*;

/**
 * lixw
 * 2023/3/30
 **/
public class WordLadder126 {
        private Node root;

        /**
         * 目标字符串节点
         */
        private Node leaf;

        class Node {
            String val;
            List<Node> next;
            boolean isLeaf = false;
            List<Node> pre;

            Node(String val) {
                this.val = val;
            }

            @Override
            public boolean equals(Object node) {
                if (node == this) return true;
                if (!(node instanceof Node)) {
                    return false;
                }
                return Objects.equals(((Node) node).val, this.val);
            }

            public void addNext(Node node) {
                if (this.next == null) {
                    this.next = new ArrayList<>();
                }
                this.next.add(node);
            }

            public void addPre(Node node) {
                if (this.pre == null) {
                    this.pre = new ArrayList<>();
                }
                this.pre.add(node);
            }

            public boolean isHead() {
                return this.pre == null;
            }
        }


        public void buildTree(String beginWord, String endWord, List<String> wordList) {
            root = new Node(beginWord);
            Queue<Node> level = new ArrayDeque<>();
            leaf = null;
            level.add(root);
            wordList.remove(beginWord);
            while (level.size() > 0 && wordList.size() > 0) {
                int size = level.size();
                Map<String, Node> used = new HashMap<>();
                for (int i = 0; i < size; i++) {
                    Node node = level.poll();
                    for (String s : wordList) {
                        if (isMatch(s, node.val)) {
                            boolean contains = used.containsKey(s);
                            Node n = used.getOrDefault(s, new Node(s));
                            n.isLeaf = s.equals(endWord);
                            if (n.isLeaf) {
                                leaf = n;
                            }
                            node.addNext(n);
                            n.addPre(node);
                            if (!contains) {
                                used.put(s, n);
                                level.add(n);
                            }
                        }
                    }
                }
                //已经用于构建的字符串节点可以删除了
                //避免构成环
                for (Node node : level) {
                    if (wordList.contains(node.val)) {
                        wordList.remove(node.val);
                    }
                }
            }
        }

        public List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
            buildTree(beginWord, endWord, wordList);
            //遍历所有的
            List<List<String>> result = new ArrayList<>();
            List<String> path = new LinkedList<>();
            path.add(endWord);
            dfs(leaf, path, result);
            return result;
        }


        private void dfs(Node node, List<String> path, List<List<String>> result) {
            if (root == node) {
                result.add(new ArrayList<>(path));
                return;
            }
            if (node == null) return;
            for (Node n : node.pre) {
                path.add(0, n.val);
                dfs(n, path, result);
                path.remove(0);
            }
        }


        private boolean isMatch(String s1, String s2) {
            int diff = 0;
            for (int i = 0; i < s1.length(); i++) {
                if (s1.charAt(i) != s2.charAt(i)) {
                    if (++diff > 1) return false;
                }
            }
            return diff == 1;
        }

    public static void main(String[] args) {
        WordLadder126 w = new WordLadder126();
        System.out.println(w.findLadders("red", "tax", Lists.newArrayList("ted", "tex", "red", "tax", "tad", "den", "rex", "pee")));

        System.out.println(w.findLadders("hot", "dog", Lists.newArrayList("hot", "dog", "dot")));
        System.out.println(w.findLadders("hit", "cog", Lists.newArrayList("hot", "dot", "dog", "lot", "log", "cog")));
        System.out.println(w.findLadders("hit", "cog", Lists.newArrayList("hot", "dot", "dog", "lot", "log")));

        List<String> l1 = Lists.newArrayList("aaaaa", "caaaa", "cbaaa", "daaaa", "dbaaa", "eaaaa", "ebaaa", "faaaa", "fbaaa", "gaaaa", "gbaaa", "haaaa", "hbaaa", "iaaaa", "ibaaa", "jaaaa", "jbaaa", "kaaaa", "kbaaa", "laaaa", "lbaaa", "maaaa", "mbaaa", "naaaa", "nbaaa", "oaaaa", "obaaa", "paaaa", "pbaaa", "bbaaa", "bbcaa", "bbcba", "bbdaa", "bbdba", "bbeaa", "bbeba", "bbfaa", "bbfba", "bbgaa", "bbgba", "bbhaa", "bbhba", "bbiaa", "bbiba", "bbjaa", "bbjba", "bbkaa", "bbkba", "bblaa", "bblba", "bbmaa", "bbmba", "bbnaa", "bbnba", "bboaa", "bboba", "bbpaa", "bbpba", "bbbba", "abbba", "acbba", "dbbba", "dcbba", "ebbba", "ecbba", "fbbba", "fcbba", "gbbba", "gcbba", "hbbba", "hcbba", "ibbba", "icbba", "jbbba", "jcbba", "kbbba", "kcbba", "lbbba", "lcbba", "mbbba", "mcbba", "nbbba", "ncbba", "obbba", "ocbba", "pbbba", "pcbba", "ccbba", "ccaba", "ccaca", "ccdba", "ccdca", "cceba", "cceca", "ccfba", "ccfca", "ccgba", "ccgca", "cchba", "cchca", "cciba", "ccica", "ccjba", "ccjca", "cckba", "cckca", "cclba", "cclca", "ccmba", "ccmca", "ccnba", "ccnca", "ccoba", "ccoca", "ccpba", "ccpca", "cccca", "accca", "adcca", "bccca", "bdcca", "eccca", "edcca", "fccca", "fdcca", "gccca", "gdcca", "hccca", "hdcca", "iccca", "idcca", "jccca", "jdcca", "kccca", "kdcca", "lccca", "ldcca", "mccca", "mdcca", "nccca", "ndcca", "occca", "odcca", "pccca", "pdcca", "ddcca", "ddaca", "ddada", "ddbca", "ddbda", "ddeca", "ddeda", "ddfca", "ddfda", "ddgca", "ddgda", "ddhca", "ddhda", "ddica", "ddida", "ddjca", "ddjda", "ddkca", "ddkda", "ddlca", "ddlda", "ddmca", "ddmda", "ddnca", "ddnda", "ddoca", "ddoda", "ddpca", "ddpda", "dddda", "addda", "aedda", "bddda", "bedda", "cddda", "cedda", "fddda", "fedda", "gddda", "gedda", "hddda", "hedda", "iddda", "iedda", "jddda", "jedda", "kddda", "kedda", "lddda", "ledda", "mddda", "medda", "nddda", "nedda", "oddda", "oedda", "pddda", "pedda", "eedda", "eeada", "eeaea", "eebda", "eebea", "eecda", "eecea", "eefda", "eefea", "eegda", "eegea", "eehda", "eehea", "eeida", "eeiea", "eejda", "eejea", "eekda", "eekea", "eelda", "eelea", "eemda", "eemea", "eenda", "eenea", "eeoda", "eeoea", "eepda", "eepea", "eeeea", "ggggg", "agggg", "ahggg", "bgggg", "bhggg", "cgggg", "chggg", "dgggg", "dhggg", "egggg", "ehggg", "fgggg", "fhggg", "igggg", "ihggg", "jgggg", "jhggg", "kgggg", "khggg", "lgggg", "lhggg", "mgggg", "mhggg", "ngggg", "nhggg", "ogggg", "ohggg", "pgggg", "phggg", "hhggg", "hhagg", "hhahg", "hhbgg", "hhbhg", "hhcgg", "hhchg", "hhdgg", "hhdhg", "hhegg", "hhehg", "hhfgg", "hhfhg", "hhigg", "hhihg", "hhjgg", "hhjhg", "hhkgg", "hhkhg", "hhlgg", "hhlhg", "hhmgg", "hhmhg", "hhngg", "hhnhg", "hhogg", "hhohg", "hhpgg", "hhphg", "hhhhg", "ahhhg", "aihhg", "bhhhg", "bihhg", "chhhg", "cihhg", "dhhhg", "dihhg", "ehhhg", "eihhg", "fhhhg", "fihhg", "ghhhg", "gihhg", "jhhhg", "jihhg", "khhhg", "kihhg", "lhhhg", "lihhg", "mhhhg", "mihhg", "nhhhg", "nihhg", "ohhhg", "oihhg", "phhhg", "pihhg", "iihhg", "iiahg", "iiaig", "iibhg", "iibig", "iichg", "iicig", "iidhg", "iidig", "iiehg", "iieig", "iifhg", "iifig", "iighg", "iigig", "iijhg", "iijig", "iikhg", "iikig", "iilhg", "iilig", "iimhg", "iimig", "iinhg", "iinig", "iiohg", "iioig", "iiphg", "iipig", "iiiig", "aiiig", "ajiig", "biiig", "bjiig", "ciiig", "cjiig", "diiig", "djiig", "eiiig", "ejiig", "fiiig", "fjiig", "giiig", "gjiig", "hiiig", "hjiig", "kiiig", "kjiig", "liiig", "ljiig", "miiig", "mjiig", "niiig", "njiig", "oiiig", "ojiig", "piiig", "pjiig", "jjiig", "jjaig", "jjajg", "jjbig", "jjbjg", "jjcig", "jjcjg", "jjdig", "jjdjg", "jjeig", "jjejg", "jjfig", "jjfjg", "jjgig", "jjgjg", "jjhig", "jjhjg", "jjkig", "jjkjg", "jjlig", "jjljg", "jjmig", "jjmjg", "jjnig", "jjnjg", "jjoig", "jjojg", "jjpig", "jjpjg", "jjjjg", "ajjjg", "akjjg", "bjjjg", "bkjjg", "cjjjg", "ckjjg", "djjjg", "dkjjg", "ejjjg", "ekjjg", "fjjjg", "fkjjg", "gjjjg", "gkjjg", "hjjjg", "hkjjg", "ijjjg", "ikjjg", "ljjjg", "lkjjg", "mjjjg", "mkjjg", "njjjg", "nkjjg", "ojjjg", "okjjg", "pjjjg", "pkjjg", "kkjjg", "kkajg", "kkakg", "kkbjg", "kkbkg", "kkcjg", "kkckg", "kkdjg", "kkdkg", "kkejg", "kkekg", "kkfjg", "kkfkg", "kkgjg", "kkgkg", "kkhjg", "kkhkg", "kkijg", "kkikg", "kkljg", "kklkg", "kkmjg", "kkmkg", "kknjg", "kknkg", "kkojg", "kkokg", "kkpjg", "kkpkg", "kkkkg", "ggggx", "gggxx", "ggxxx", "gxxxx", "xxxxx", "xxxxy", "xxxyy", "xxyyy", "xyyyy", "yyyyy", "yyyyw", "yyyww", "yywww", "ywwww", "wwwww", "wwvww", "wvvww", "vvvww", "vvvwz", "avvwz", "aavwz", "aaawz", "aaaaz");
        System.out.println(w.findLadders("aaaaa", "ggggg", l1));
    }
}
